package leetcode_1_200;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_131 {
    public static void main(String[] args) {
        System.out.println(partition("aab"));
        System.out.println(partition("a"));
    }
    private static List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        f(ans,new ArrayList<>(), s, 0);
        return ans;
    }
    private static void f(List<List<String>> ans, List<String> list, String s, int index){
        int len = s.length();
        for (int i = index; i < len; i++) {
            StringBuilder sb = new StringBuilder(s.substring(index, i + 1));
            String s1 = sb.toString();
            String s2 = sb.reverse().toString();
            if (s1.equals(s2)){
                ArrayList<String> newL = new ArrayList<>(list);
                newL.add(s1);
                if (i == len - 1){
                    ans.add(newL);
                    return;
                }
                f(ans, newL, s, i + 1);
            }
        }
    }
}
